#include<vector>
#include<queue>
#include<unordered_set>
using namespace std;

class Solution {
    struct Cell {
        int x, y, h;
        Cell(int x_,int y_,int h_):x(x_),y(y_),h(h_){}
    };
    struct Comapre {
        bool operator()(const Cell& left, const Cell& right) {
            return left.h > right.h;
        }
    };

public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.size() < 1) return 0;
        priority_queue<Cell,vector<Cell>,Comapre>queue;
        unordered_set<int>visited;
        int rows = heightMap.size();
        int cols = heightMap[0].size();
        for (int i = 0; i < rows; ++i) {
            queue.emplace(i, 0, heightMap[i][0]);
            visited.insert(i * cols + 0);
            queue.emplace(i, cols-1, heightMap[i][cols-1]);
            visited.insert(i * cols + cols - 1);
        }
        for (int i = 0; i < cols; ++i) {
            queue.emplace(0, i, heightMap[0][i]);
            visited.insert(i);
            queue.emplace(rows - 1, i, heightMap[rows - 1][i]);
            visited.insert((rows - 1) * cols + i);
        }
        int res = 0;
        vector<vector<int>>ops = { {-1,0},{1,0},{0,-1},{0,1} };
        while (!queue.empty()) {
            auto cell = queue.top();
            queue.pop();
            for (auto& op : ops) {
                int i = cell.x + op[0];
                int j = cell.y + op[1];
                if (i < 0 || i >= rows | j < 0 || j >= cols)
                    continue;
                int key = i * cols + j;
                if (visited.find(key) != visited.end())
                    continue;
                int h = heightMap[i][j];
                if (h < cell.h) {
                    res += cell.h - h;
                    h = cell.h;
                }
                visited.insert(key);
                queue.emplace(i, j, h);
            }
        }
        return res;
    }
};